An abstract data type is a data type defined in effect by semantics of operations performed on the data type. In a program, abstract data types may only be accessed by these operations. Implementations of abstract data types and the operations that define the abstract data types are provided separately and may not be exposed to a programmer. There can be many different implementations for an abstract data type; however, the different implementations each support and honor the semantics of the operations.
The choice of implementation for abstract data types can greatly affect the performance of a program. Poor choice of implementation often leads to poor performance of the program. There may be no one-size-fits-all implementation of an abstract data type which performs best for every use case.
Typically, programmers choose the best implementation of the abstract data types for programs. Programmers may choose an existing implementation from an available library or program their own implementation.
Described herein are techniques for providing implementations for abstract data types.